package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         321,
		Discription: "从两个值为0...9的数组里选k个数，使其组成的数最大，同时保持各数位索引相对位置不变",
		Level:       4,
		Labels: map[string]int{
			"单调栈":     1,
			"定长单调栈": 1,
			"双指针滑动": 1,
		},
	})
}

//首先根据两个数组的长度、k，确定第一个数组中至多和至少要选几个数，第二个数组选取的数的数量也随之确定
//遍历两个数的长度组合（O（n））
//在各自指定长度下，分别取各自的定长单调栈
//通过双指针滑动合并单调栈
func MaxNumber(nums1 []int, nums2 []int, k int) []int {
	maxLen1 := min(len(nums1), k)
	minLen1 := max(0, k-len(nums2))
	res := make([]int, k)
	for length := minLen1; length <= maxLen1; length++ {
		s1 := getDecS(nums1, length)
		s2 := getDecS(nums2, k-length)

		i := 0
		j := 0
		index := 0
		bigger := false
		tempRes := make([]int, k)
		for index < k {
			if i == length {
				tempRes[index] = s2[j]
				j++
			} else if j == k-length {
				tempRes[index] = s1[i]
				i++
			} else {
				choose := func(i, j int) bool {
					if s1[i] != s2[j] {
						return s1[i] > s2[j]
					}

					i++
					j++
					for i < len(s1) && j < len(s2) {
						//合并时碰到相同的情况，谁后面的值更大，就优选选谁
						if s1[i] == s2[j] {
							i++
							j++
						} else {
							return s1[i] > s2[j]
						}
					}

					//在判断数组后续谁更大时，有一方数组越界
					//如果没越界的数组后面第一个不相等的数比之前更小，那么顺序无所谓；如果更大，就必须优选选没越界的数组
					if j < len(s2) {
						for j < len(s2) && s2[j] == s2[j-1] {
							j++
						}

						if j < len(s2) && s2[j] > s1[i-1] {
							return false
						}
					}

					return true
				}

				if choose(i, j) {
					tempRes[index] = s1[i]
					i++
				} else {
					tempRes[index] = s2[j]
					j++
				}
			}

			//判断是否比已有的组合大
			if !bigger {
				if tempRes[index] < res[index] {
					break
				}

				if tempRes[index] > res[index] {
					bigger = true
				}
			}

			index++
		}

		if index == k {
			res = tempRes
		}
	}

	return res
}

//获得定长单调栈
func getDecS(nums []int, n int) []int {
	s := make([]int, 0)
	for index, val := range nums {
		//同时满足三种情况，才可以出栈
		//1. 栈不为空
		//2. 剩下的数组长度足够组成长度为n的单调栈
		//3. 当前值大于栈顶
		for len(s) > 0 && len(s)-1+len(nums)-index >= n && val > s[len(s)-1] {
			s = s[:len(s)-1]
		}

		//长度够了就无需进栈
		if len(s) < n {
			s = append(s, val)
		}
	}

	return s
}
